package com.chenxys.algorithm.newbie;

/**
 * <p>
 *      前缀和，给定一个数组和两个下标，获取两个下标之间的和
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/24/23 8:33 PM
 * @Copyright ©
 */
public class PreSum {
    public static class RangeSumV2{
        private int[] preSum;

        /**
         * <p>
         *     生成累加和的一维数组:数组大长度与原数组长度一致，数组元素第0个为原数组第0个，第一个为原数组第0个 + 第一个...
         * </p>
         * @param array 原数组
         */
        public RangeSumV2(int[] array){
            int N = array.length;
            preSum = new int[N];
            preSum[0] = array[0];
            for (int i = 1; i < N; i++) {
                // 数组前一位的值 + 原数组当前位的值
                preSum[i] = preSum[i - 1] + array[i];
            }
        }

        /**
         * <p>
         *     返回两下标数组和
         * </p>
         * @param L left下标
         * @param R right下标
         * @return 两下标元素和
         */
        public int rangeSum(int L, int R){
            return L == 0 ? preSum[R] : preSum[R] - preSum[L-1];
        }
    }

    public static void main(String[] args) {
        int[] arr = {7, 1, 3, 5, 1, 6, 8, 1, 3, 5, 7, 5, 6};
        RangeSumV2 rangeSumV2 = new RangeSumV2(arr);
        System.out.println(rangeSumV2.rangeSum(1, 2));
    }

}
